package _general.lefttree;

import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

import _general.lefttree.Node.ChildType;

public class LeftTree<E> extends AbstractQueue<E> implements Queue<E> {

	private Node<E> rootNode = null;

	private int size = 0;

	private final Comparator<? super E> comparator;

	private int elementsHash = 7;

	private LeftTree(final Comparator<? super E> comparator) {
		if (comparator == null) {
			throw new IllegalArgumentException("Comparator must not be null");
		}
		this.comparator = comparator;
	}

	/**
	 * Creates a new left tree based on a {@link Comparable} element type using
	 * its natural ordering.
	 * 
	 * @param <E>
	 *            The element type
	 * @return The created left tree, which is empty
	 */
	public static <E extends Comparable<? super E>> LeftTree<E> getInstance() {
		return new LeftTree<E>(new Comparator<E>() {
			@Override
			public int compare(E o1, E o2) {
				return o1.compareTo(o2);
			}
		});
	}

	/**
	 * Creates a new left tree based on any element type using a given
	 * {@link Comparator}.
	 * 
	 * @param <E>
	 *            The element type
	 * @param comparator
	 *            The comparator used to compare elements
	 * @return The created left tree, which is empty
	 */
	public static <E> LeftTree<E> getInstance(
			final Comparator<? super E> comparator) {
		return new LeftTree<E>(comparator);
	}

	@Override
	public boolean contains(Object o) {
		if (o == null) {
			return false;
		}

		@SuppressWarnings("unchecked")
		final E compareWith = (E) o; // must be an E or an exception occurs

		for (E element : this) {
			if (this.comparator.compare(element, compareWith) == 0) {
				return true;
			}
		}
		return false;
	}

	@Override
	public Iterator<E> iterator() {
		return new LeftTreeIterator();
	}

	@Override
	public int size() {
		return this.size;
	}

	@Override
	public boolean offer(E e) {
		this.elementsHash += 13 * e.hashCode();
		this.rootNode = Node.create(null, null, e).mergeWith(this.rootNode,
				this.comparator);
		this.size++;
		return true;
	}

	@Override
	public E peek() {
		if (size == 0) {
			return null;
		}
		return this.rootNode.getContent();
	}

	@Override
	public E poll() {
		if (size == 0) {
			return null;
		}
		final E result = this.rootNode.getContent();
		do {
			this.elementsHash += 17 * this.rootNode.getContent().hashCode();
			if (--size > 0) {
				this.rootNode = this.rootNode.getChild(ChildType.LEFT)
						.mergeWith(this.rootNode.getChild(ChildType.RIGHT),
								this.comparator);
			} else {
				this.rootNode = null;
			}
		} while (this.peek() != null && this.comparator.compare(result, this.peek()) == 0);

		return result;
	}

	@Override
	public String toString() {
		if (this.size() == 0) {
			return "[]";
		}
		return this.rootNode.toString();
	}

	private class LeftTreeIterator implements Iterator<E> {

		private int elementsHash = LeftTree.this.elementsHash;

		private final Queue<Node<E>> elements;

		private Node<E> lastElementReturned = null;

		private LeftTreeIterator() {
			this.elements = new LinkedList<Node<E>>();

			this.addElements(this.elements, LeftTree.this.rootNode);
		}

		private void addElements(Queue<Node<E>> elementQueue, Node<E> node) {
			if (node == null) {
				return;
			}
			this.addElements(elementQueue, node.getChild(ChildType.LEFT));
			elementQueue.add(node);
			this.addElements(elementQueue, node.getChild(ChildType.RIGHT));
		}

		@Override
		public boolean hasNext() {
			return !this.elements.isEmpty();
		}

		@Override
		public E next() {
			if (this.elementsHash != LeftTree.this.elementsHash) {
				throw new ConcurrentModificationException();
			}
			if (this.elements.isEmpty()) {
				throw new NoSuchElementException();
			}
			this.lastElementReturned = this.elements.poll();
			return this.lastElementReturned.getContent();
		}

		@Override
		public void remove() {
			if (this.elementsHash != LeftTree.this.elementsHash) {
				throw new ConcurrentModificationException();
			}
			if (this.lastElementReturned == null) {
				throw new IllegalStateException();
			}

			final Node<E> subtreesMerges = Node.merge(this.lastElementReturned
					.getChild(ChildType.LEFT), this.lastElementReturned
					.getChild(ChildType.RIGHT), LeftTree.this.comparator);
			if (this.lastElementReturned.getParent() == null) {
				LeftTree.this.rootNode = subtreesMerges;
			} else {
				this.lastElementReturned.detachFromParent();
				LeftTree.this.rootNode = LeftTree.this.rootNode.mergeWith(
						subtreesMerges, LeftTree.this.comparator);
			}
			LeftTree.this.size--;
			LeftTree.this.elementsHash += 17 * this.lastElementReturned
					.getContent().hashCode();

			this.lastElementReturned = null;
		}

	}

}
